1. Field of the Invention
The present invention relates to decoding apparatuses, decoding methods and programs. More particularly, the present invention relates to a decoding apparatus that is capable of decoding a plurality of LDPC (Low Density Parity Check) codes having structures different from each other and has a small circuit size. The present invention also relates to a decoding method to be adopted by the decoding apparatus and a program implementing the decoding method.
2. Description of the Related Art
A communication system adopts a coding technique in order to carry out a reliable communication through a communication channel having noises. In a wireless system (or a radio system) such as a satellite network for example, there are many noise sources attributed to geographical and environmental causes. Each of communication channels can be regarded as a channel having a fixed capacitance, can be regarded as a channel capable of representing the number of bits per symbol at a certain SNR (Signal to Noise Ratio) and prescribes a theoretical upper limit which is known as a Shannon limit. For this reason, the coding design has an objective to achieve a rate approaching the Shannon limit. This objective has a particularly close relation with a limited-bandwidth satellite system.
In recent years, there have been developed coding methods each exhibiting a performance close to the Shannon limit. Each of the coding methods is also referred to as the so-called turbo coding technique adopted in a coding process based on turbo codes such as PCCCs (Parallel Concatenated Convolutional Codes) and SCCCs (Serially Concatenated Convolutional Codes). While these turbo codes are being developed, LDPC codes (Low Density Parity Check codes) has been drawing much attention. The LDPC codes are codes used in a coding method which has been known from a long time ago.
The LDPC code was first proposed by R. G. Gallager in “Low Density Parity Check Codes,” Cambridge, Mass., MIT Press, 1963. Thereafter, the LDPC code again drew attention as described in D. J. C Mackay, “Good error correcting codes based on very parse matrices,” submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999 and M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs,” in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998.
Results of research conducted in recent years have been gradually indicating that, in the case of the LDPC code, by increasing the code length, it is possible to demonstrate a performance close to the Shannon limit in the same way as the turbo code. In addition, the LDPC code has a property showing that the minimum distance is proportional to the code length. Thus, the LDPC code is characterized in that the LDPC code offers merits of a good block error probability characteristic and all but no occurrence of the so-called error floor phenomenon almost. The error floor phenomenon is a phenomenon observed in a decoding characteristic of codes such as the turbo code.
The LDPC code is explained concretely as follows. It is to be noted that the LDPC code is a linear code and is not necessarily a two-dimensional code. In the following description, however, the LDPC code is explained as a two-dimensional code.
The most prominent characteristic of the LDPC code is that a parity check matrix defining the LDPC code is a sparse matrix. The sparse matrix is a matrix in which the number of elements each having a value of 1 is very small. Let notation H denote the sparse parity check matrix. FIG. 1 is a diagram showing a typical sparse parity check matrix H. As shown in the diagram of FIG. 1, the Hamming weight of each column is three whereas the Hamming weight of each row is six. The Hamming weight of a column or a row is the number of matrix elements each included in a column or a row as an element each having a value of 1.
An LDPC code defined by a parity check matrix H having a constant Hamming weight for each column and a constant Hamming weight for each row as described above is referred to as a regular LDPC code. On the other hand, an LDPC code defined by a parity check matrix H having a Hamming weight varying from column to column and a Hamming weight varying from row to row is referred to as an irregular LDPC code.
A coding process based on such an LDPC code is carried out by creating a generated matrix G on the basis of the parity check matrix H defining the LDPC code. Then, the generated matrix G is multiplied by a two-dimensional information message u in order to produce a coded word c. To put it concretely, a coding apparatus for carrying out a coding process based on the LDPC code creates a generated matrix G for which the equation GHT=0 holds true with respect to a rearranged matrix HT derived from the parity check matrix H defining the LDPC code. If the generated matrix G is a k×n matrix, the coding apparatus then multiplies the generated matrix G by an information message of k bits in order to produce a coded word c (=uG) composed of n bits. In the following description, the information message composed of k bits is also referred to as a vector u. The coding apparatus finally transmits the coded word c by mapping each coded-word bit having a value of 0 onto +1 and each coded-word bit having a value of 1 onto −1 to a receiver through a communication line determined in advance. In a word, the coding apparatus encodes the information message u into the coded word c on the basis of the LDPC code defined by the parity check matrix H.
It is to be noted that, if the coded word c composed of n bits is an organization code matching an n-bit sequence composed of an information message of k bits followed by (n-k) parity bits for example, in the (n-k)−row×n-column parity check matrix H composed of (n-k) rows and n columns as shown in a diagram of FIG. 2, the (n-k)−row×k-column matrix portion corresponding to the k-bit information message u of the coded word composed of n bits is referred to as an information portion whereas the (n-k)−row×(n-k)−column matrix portion corresponding to the (n-k) parity bits of the coded word composed of n bits is referred to as a parity portion. If the parity portion is a lower triangular matrix or an upper triangular matrix, the process to code the information message u by adoption of the coding method based on the LDPC code is carried out by making use of the parity check matrix H defining the LDPC code.
That is to say, as shown in the diagram of FIG. 2, the parity check matrix H includes the information portion and a lower triangle matrix serving as the parity portion whereas every element of the lower triangle matrix serving as the parity portion is 1. In this case, the sequence of parity bits is found as follows. First of all, the first parity bit of the parity-bit sequence of the coded word c has a value obtained as a result of carrying out an EXOR (exclusive logical sum) process on bits each included in the information message u as a bit corresponding to a matrix element included in the first row of the information portion of the parity check matrix H as an element having a value of 1.
Then, the second parity bit of the parity-bit sequence of the coded word c has a value obtained as a result of carrying out an EXOR process on the first parity bit of the parity-bit sequence and message bits each included in the information message u as a bit corresponding to a matrix element included in the second row of the information portion of the parity check matrix H as an element having a value of 1.
Subsequently, the third parity bit of the parity-bit sequence of the coded word c has a value obtained as a result of carrying out an EXOR process on the first and second parity bits of the parity-bit sequence and message bits each included in the information message u as a bit corresponding to a matrix element included in the third row of the information portion of the parity check matrix H as an element having a value of 1.
Thereafter, the fourth and subsequent parity bits of the parity-bit sequence are found in the same way. Speaking generally, the ith parity bit of the parity-bit sequence of the coded word c has a value obtained as a result of carrying out an EXOR process on the first to (i−1)th parity bits of the parity-bit sequence and message bits each included in the information message u as a bit corresponding to a matrix element included in the ith row of the information portion of the parity check matrix H as an element having a value of 1.
The (n-k) parity bits of the parity-bit sequence are computed as described above and the parity-bit sequence is then put at a location following the information message composed of k bits in order to generate a coded word c composed of n bits.
On the other hand, a decoding process making use of an LDPC code can also be carried out in accordance with a message passing algorithm based on belief propagations on the so-called Tanner graph composed of variable nodes also each referred to as a message node and check nodes. The message passing algorithm is an algorithm proposed by Gallager as an algorithm called probabilistic decoding. Herein under the variable nodes and check nodes are simply referred to as nodes, arbitrarily.
In the case of the probabilistic decoding algorithm, however, a message passed between nodes is a real value. Thus, in order to analytically solve the message, it is necessary to track the probability distribution of the message which has a continuous value. That is to say, it is necessary to carry out an extremely difficult analysis. In order to resolve this problem, Gallager has proposed algorithms A and B as algorithms each used for decoding an LDPC code or, strictly speaking, decoding data already encoded by making use of an LDCP code.
The decoding processing to decode data coded by making use of an LDPC code is typically carried out in accordance with a procedure represented by a flowchart shown in FIG. 3. In the following description, the processing to decode the data coded by making use of an LDPC code is also referred to simply as a process to decode an LDPC code whereas an LDPC code serving as a subject of decoding means data already encoded by making use of an LDPC code. It is to be noted that, in the procedure, notation U0 (u0i) denotes the ith value of received data coded on the basis of the LDPC code having a certain code length, notation uj denotes the jth message output from a check node or, strictly speaking, a message output from a jth edge connected to the check node whereas notation vi denotes the ith message output from a variable node or, strictly speaking, a message output from an ith edge connected to the variable node. In addition, in this case, a message is a real value used for expressing the so-called log likelihood ratio or the like as a value representing the likelihood of the value 0.
As shown in FIG. 3, the flowchart representing the procedure of the decoding processing begins with a step S101 at which a data value U0 (u0i) is received whereas each of a message uj and a variable k is initialized to 0. The variable k is an integer representing the number of repetitive processing. Then, the flow of the decoding process goes on to a step S102. At the step S102, the received data value U0 (u0i) is used in conjunction with messages ui for carrying out a process at a variable node in accordance with Eq. (1) in order to find a message vi. Then, the message vi is used for carrying out a process at a check node in accordance with Eq. (2) in order to find, a message uj.
                              v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          (        1        )                                          tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                                          ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Notation dv used in Eq. (1) denotes a parameter representing the number of elements each having a value of 1 in the vertical (or column) direction whereas notation dc used in Eq. (2) denotes a parameter representing the number of elements each having a value of 1 in the horizontal (or row) direction. That is to say, notations dv and dc denote parameters representing the Hamming weight of each column and the Hamming weight of each row respectively. The values of these parameters dv and dc can be arbitrarily selected. In the case of a code (3, 6) for example, the value of the Hamming weight of each column is set at 3 (that is, dv=3) whereas the value of the Hamming weight of each row is set at 6 (that is, dc=6).
It is to be noted that, in the summation process according to Eq. (1), a message input from an edge making an attempt to output a message is not used as a subject of the process. Thus, the range of the summation process starts from 1 and ends at (dv−1). By the same token, in the multiplication process according to Eq. (2), a message input from an edge making an attempt to output a message is not used as a subject of the process. Thus, the range of the multiplication process starts from 1 and ends at (dc−1). In addition, the multiplication process to find the value of the message uj in accordance with Eq. (2) can be carried out in accordance with Eqs. (3) and (4) as follows. A table of values 1 of a function R (v1, v2) for two given inputs v1 and v2 is created in advance as a table according to Eq. (3). As indicated by Eq. (3), the value x of the function R (v1, v2) is a function of inputs v1 and v2. Then, the value of the message uj can be found by using the value x, which is found from the table, in a recursive manner according to Eq. (4).x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1, v2)  (3)uj=R(v1, R(v2, R(v3, . . . R(vdc−2, vdc−1))))  (4)
In addition, at the step S102, the variable k is incremented by 1. Then, the flow of the decoding process goes on to a step S103. At the step S103, the variable k is compared with a repetitive decoding count N determined in advance in order to produce a result of determination as to whether or not the variable k is equal to or greater than the repetitive decoding count N. If the determination result produced by the process carried out at the step S103 indicates that the variable k is neither equal to nor greater than the repetitive decoding count N determined in advance, the flow of the decoding process goes back to the step S102 to repeat the processes of the steps S102 and S103.
If the determination result produced by the process carried out at the step S103 indicates that the variable k is either equal to or greater than the repetitive decoding count N determined in advance, on the other hand, the flow of the decoding process goes on to a step S104 at which a message v is found by carrying out a process according to Eq. (5) as a decoding result to be output eventually. Then, the decoding processing to decode data coded by making use of an LDPC code is ended.
                    v        =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          (        5        )            
The computation process according to Eq. (5) is different from the computation process according to Eq. (1) in that the computation process according to Eq. (5) is carried out by making use of messages uj from all edges connected to the variable node.
In the decoding processing to decode data coded by making use of an LDPC code, in the case of a (3, 6) code for example, messages are exchanged between nodes as shown in a diagram of FIG. 4. It is to be noted that, in the diagram of FIG. 4, each node indicated by the “=” equal symbol is a variable node at which the summation process according to Eq. (1) is carried out. On the other hand, each node indicated by the “+” plus operator is a check node at which the multiplication process according to Eq. (2) is carried out.
Particularly, in accordance with algorithm A cited earlier, a message is made two dimensional and, at a check node indicated by the “+” plus operator, an exclusive logical sum process is carried out on (dc−1) input messages vi which are supplied to the check node whereas, at a variable node indicated by the “=” equal symbol, the sign of received data R is inverted before the data R is output if (dv−1) input messages uj supplied to the variable node have all different bit values.
In addition, in recent years, research on implementation of a method for performing a process to decode data coded by making use of an LDPC code is carried out. Before the method for carrying out processing to decode data coded by making use of an LDPC code is described, first of all a model of the processing to decode data coded by making use of an LDPC code is created and explained.
FIG. 5 is a diagram showing a typical parity check matrix H defining the LDPC code of a (3, 6) code as an LDPC code having an encoding ratio of 1/2 and a code length of 12. The parity check matrix H shown in the diagram of FIG. 5 as a matrix defining the LDPC code can be expressed by a Tanner graph like one shown in a diagram of FIG. 6. In the diagram of FIG. 6, each node indicated by the “=” equal symbol is a variable node whereas each node indicated by the “+” plus operator is a check node. The check and variable nodes correspond to the rows and the columns in the parity check matrix H. A line connecting a check node and a variable node to each other is referred to as an edge which corresponds to a matrix element having a value of 1. That is to say, if a matrix element at an intersection existing in the parity check matrix H as an intersection of the jth row and the ith column has a value of 1, the ith variable node from the top of the diagram of FIG. 6 (that is, the ith node indicated by the “=” equal notation) and the jth check node from the top of the diagram of FIG. 6 (that is, the jth node indicated by the “+” plus operator) are connected to each other by an edge corresponding to the intersection at which the matrix element has a value of 1. An edge connecting a variable node and a check node to each other indicates that the bit included in the received data coded by making use of an LDPC code as a bit associated with the variable node has a condition of constraint with respect to the check node. It is to be noted that the Tanner graph shown in the diagram of FIG. 6 expresses the parity check matrix H shown in the diagram of FIG. 5 as described above.
A Sum Product Algorithm serving as the method for decoding data coded by making use of an LDPC code is an algorithm for carrying out the processes of the variable and check nodes repeatedly.
At a variable node, the summation process represented by Eq. (1) as the process of a variable node is carried out as shown in the diagram of FIG. 7. In the summation process shown in the diagram of FIG. 7, a message vi corresponding to the ith edge existing among edges connected to the variable node is computed from messages u1 and u2 coming from the remaining edges connected to the variable node and received data value u0i. A message corresponding to any other edge is also computed in the same way.
Before the process carried out at a check node is explained, Eq. (2) is rewritten into Eq. (6) by making use the relation a×b=exp {ln(|a|)+ln(|b|)} sign(a)×sign(b) where sign(x) has a value of 1 (or the logic value of 0) for x≧0 or a value of −1 (or the logic value of 1) for x<0.
                                                                        u                j                            =                            ⁢                              2                ⁢                                                                  ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                                                                          ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                                              ∑                                                          i                              =                              1                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                      ln                            ⁡                                                          (                                                                                                                                tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                                                                              )                                                                                                      }                                            ×                                                                        ∏                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                                                                  ⁢                                                  sign                          ⁡                                                      (                                                          tanh                              ⁡                                                              (                                                                                                      v                                    i                                                                    2                                                                )                                                                                      )                                                                                                                ]                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                                                          ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
In addition, for x≧0, let us define a nonlinear function φ(x)=−ln (tan h(x/2)). In this case, the inverse function φ−1(x) of the nonlinear function φ(x) can be expressed as follows: φ−1(x)=2 tan h−1 (e−x). Thus, Eq. (6) can be rewritten into Eq. (7) from the equation φ−1(x)=2 tan h−1(e−x) as follows:
                              u          j                =                                            ϕ                              -                1                                      (                                          ∑                                  i                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                              ϕ                ⁡                                  (                                                                                v                      i                                                                            )                                                      )                    ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                                                  ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
At a check node, a check-node process according to Eq. (7) is carried out as shown in the diagram of FIG. 8. In the multiplication process shown in the diagram of FIG. 8, a message uj corresponding to the jth edge existing among edges connected to the check node is computed from messages v1, v2, v3, v4 and v5 coming from the remaining edges connected to the check node. A message corresponding to any other edge is also computed in the same way.
It is to be noted that the nonlinear function φ(x) can also be expressed as follows: φ(x)=ln((ex+1)/(ex−1)). In this case, for x>0, φ(x)=φ−1(x). That is to say, the processing result of execution of the nonlinear function φ(x) is equal to the processing result of execution of the inverse function φ−1(x) of the nonlinear function φ(x). In actuality, hardware is used for implementing each of the nonlinear function φ(x) and the inverse function φ−1(x) of the nonlinear function φ(x). The hardware used for implementing each of the nonlinear function φ(x) and the inverse function φ−1(x) of the nonlinear function φ(x) is typically a LUT (Look Up Table). Thus, in this case, a LUT common to the nonlinear function φ(x) and the inverse function φ−1(x) of the nonlinear function φ(x) can be used.
In addition, the process carried out at a variable node as the summation process according to Eq. (1) can be divided into the summation process according to Eq. (5) and a subtraction process according to Eq. (8).vi=v−udv  (8)
Thus, by repeating the processes according to Eqs. (5) and (8), the process of a variable node can be repeated, that is, the variable-node process according to Eq. (1) can be repeated. By the same token, by repeating the process according to Eq. (7), the process of a check node can be repeated. In this case, the result of the last process according to Eq. (8) obtained as a result of repeating the processes according to Eqs. (5) and (8) can be used as it is as the final result of the decoding processing.
If the Sum Product Algorithm is implemented by hardware as an algorithm for a decoding apparatus, it is necessary to repeat the variable-node process and the check-node process at an appropriate operating frequency by making use a circuit having a proper size. The variable-node process is the process carried out at every variable node in accordance with Eq. (1) or Eqs. (5) and (8) whereas the check-node process is the process carried out at every check node in accordance with Eq. (7).
An example of such a decoding apparatus is explained as follows.
The algorithm used for decoding data coded by making use of an LDPC code is characterized in that the algorithm allows a full parallel-processing decoding apparatus with a very high performance to be implemented. However, the full parallel-processing decoding apparatus intended for data with a large code length has an extremely large circuit size so that it is difficult to implement the apparatus.
In order to solve this problem, in recent years, there has been proposed an LDPC code having a structure suitable for implementation of a decoding apparatus having a practical circuit size as an LDPC code to be used in a communication system such as DVB-S.2 (ETSI EN302307). For this reason, the proposed LDPC code is referred to as DVB-S.2 LDPC code in the following description.
The DVB-S.2 LDPC code can be defined by a matrix having a structure obtained by rearranging the rows and the columns in the parity check matrix as described below.
That is to say, the DVB-S.2 LDPC code can be expressed by a parity check matrix having a structure obtained by combining a plurality of configuration matrixes which include a P×P unit matrix (where P=360), a P×P semi unit matrix, a P×P shift matrix, a P×P sum matrix and a P×P zero matrix. A semi unit matrix is a unit matrix in which each of one or more matrix elements each having a value of 1 is set at 0. A shift matrix is a matrix obtained as a result of carrying out a cyclic shift operation on a unit matrix or a semi unit matrix. A sum matrix is a matrix obtained by carrying out a matrix addition operation on at least two of the unit matrix, the semi unit matrix and the shift matrix. It is to be noted that, in the following description, the parity check matrix having such a structure is referred to as a parity check matrix composed of configuration matrixes each having a P×P structure whereas an LDPC code defined by a parity check matrix composed of configuration matrixes each having a P×P structure is referred to as a P code.
By making use of such a P code, it is possible to implement a decoding apparatus for simultaneously processing P bits representing P received values respectively and P bits representing P messages respectively.
In order to make the following explanation easy to understand, however, the explanation is given for P=6. FIG. 9 is a diagram showing a parity check matrix H defining an LDPC code with a coding ratio of 2/3 and a code length of 108. The parity check matrix H shown in the diagram of FIG. 9 is a typical parity check matrix composed of configuration matrixes each having a 6×6 structure. In order to make each of the configuration matrixes each having a 6×6 structure easy to recognize, gaps are provided between the 6×6 configuration matrixes in the parity check matrix H shown in the diagram of FIG. 9. In order to make the diagram of FIG. 9 easy to look at, each of the matrix elements each having a value of 0 in the parity check matrix H is represented by a period “.”. That is to say, the parity check matrix shown in the diagram of FIG. 9 has a structure obtained by combining a plurality of configuration matrixes which include 6×6 unit matrixes, 6×6 semi unit matrixes, 6×6 shift matrixes, 6×6 sum matrixes and a 6×6 zero matrixes. As described earlier, a semi unit matrix is a unit matrix in which each of one or more matrix elements each having a value of 1 is set at 0.
FIG. 10 is a block diagram showing a typical related-art decoding apparatus for decoding data coded by making use of an LDPC code described above as an LDPC code for P=6.
The configuration of the typical decoding apparatus shown in the block diagram of FIG. 10 includes a received-value buffer 200, a received-value storage memory 201, a node processing section 202, a shift section 203, a message storage memory 204 and a decoding-result storage memory 205.
The received-value buffer 200 is a buffer for storing data D200 received from a communication line as data having a size of one code before the data D200 is transferred to the received-value storage memory 201 as data D201. Depending on a transmission method for transmitting the data D200 to the received-value buffer 200, a process to rearrange code bits of the data D200 stored in the received-value buffer 200 may be carried out in some cases.
The data D201 is read out from the received-value storage memory 201 in accordance with the order of the columns of the parity check matrix H shown in the diagram of FIG. 9 at the same time in six-piece units with each piece composed of 6 bits. That is to say, the data D201 is read out from the received-value storage memory 201 in units which are each a matrix composed of six rows and six columns and supplied to the node processing section 202 as received data D202.
The node processing section 202 employs six node processors denoted by reference numerals 210-1 to 210-6 respectively. Each of the six node processors 210-1 to 210-6 carries out the check-node process or the variable-node process on a predetermined one of six pieces of data D202 read out from the received-value storage memory 201 and a predetermined one of six messages D205 received from the message storage memory 204 at the same time in accordance with a command issued by a control section not shown in the block diagram of FIG. 10 and outputs messages D203 to the shift section 203 as results of the processes. That is to say, the node processors 210-1 to 210-6 supply six messages D203 respectively to the shift section 203 as results of the processes carried out concurrently. In addition, the node processors 210-1 to 210-6 also output respectively six decoding results D206 of the variable-node processes carried out by the node processors 210-1 to 210-6 at the same time to the decoding-result storage memory 205 simultaneously.
When the node processors 210-1 to 210-6 employed in the node processing section 202 supply six messages D203 respectively to the shift section 203, a control section not shown in the block diagram of FIG. 10 provides the shift section 203 with information indicating that edges corresponding to the six messages D203 are each an edge for which some cyclic shift operations have been carried out on a configuration matrix such as a unit matrix serving as an element matrix of the parity check matrix H shown in the diagram of FIG. 9. On the basis of this information, the shift section 203 carries out a cyclic shift operation to rearrange the six messages D203 and outputs six messages D204 to the message storage memory 204 as a result of the operation.
In the message storage memory 204, the 6 messages D204 received from the shift section 203 are stored at an address specified by a control section not shown in the block diagram of FIG. 10. The message storage memory 204 outputs six pieces of data read out from an address specified by a control section not shown in the block diagram of FIG. 10 to the node processing section 202 as six messages D205.
The decoding-result storage memory 205 is used for storing the six decoding results D206 of the variable-node processes carried out by the node processors 210-1 to 210-6 of the node processing section 202 at the same time. The six decoding results D206 are actually data of 6 bits. After the decoding processing is completed, the data of 6 bits is output as a decoding result D207.
It is to be noted that, by properly controlling the order to write data into each of the memories, the order to read out data from each of the memory and the shift quantity, the typical decoding apparatus shown in the block diagram of FIG. 10 is capable of decoding not only single code but also other code having identical structures.
FIG. 11 is a block diagram showing a typical configuration of each of the six node processors 210-1 to 210-6 employed in the node processing section 202. In the following, if it is not necessary to distinguish the six node processors 210-1 to 210-6 from each other, each of the six node processors 210-1 to 210-6 is denoted merely by a generic reference numeral 210.
The node processor 210 having a typical configuration shown in the block diagram of FIG. 11 is capable of carrying out the variable-node process according to Eq. (1) and the check-node process according to Eq. (7) alternately by switching the process from one to the other.
The node processor 210 has two input ports P301 and P302 each used for receiving a message or data from an external source. To be more specific, in the typical decoding apparatus shown in the block diagram of FIG. 10, the input port P301 is a port used for receiving data D202 from the received-value storage memory 201 whereas the input port P302 is a port used for receiving a message D205 from the message storage memory 204.
In addition, the node processor 210 also has 2 output ports P303 and P304 each used for outputting a message or a process result. To be more specific, in the typical decoding apparatus shown in the block diagram of FIG. 10, the output port P303 is a port used for outputting a message D203 to the shift section 203 whereas the output port P304 is a port used for supplying a decoding result D206 to the decoding-result storage memory 205.
On top of that, the node processor 210 also employs selectors 301, 316 and 318 which each have V and C input terminals. With each of the selectors 301, 316 and 318 selecting the V input terminal, the node processor 210 carries out the variable-node process. With each of the selectors 301, 316 and 318 selecting the C input terminal, on the other hand, the node processor 210 carries out the check-node process.
First of all, the variable-node process carried out by the node processor 210 serving as a variable node is explained.
The node processor 210 receives one-column messages D205 originated by check nodes from the message storage memory 204 of the typical decoding apparatus shown in the block diagram of FIG. 10 through the input port P302. The messages D205 are sequentially supplied to the selector 301 one message after another as messages D301 (or messages uj). The selector 301 supplies the message D301 as a message D306 to an adder 302. The adder 302 also receives data D323 output by a selector 317. The adder 302 adds the data D323 output by the selector 317 to the message D306 output by the selector 301 in order to produce a sum which is then stored in a register 303.
If the selector 317 has selected its input terminal connected to the register 303 outputting data D307, the adder 302 adds the data D307 supplied by the register 303 to the adder 302 by way of the selector 317 to the message D306 output by the selector 301 in order to produce a sum which is then again stored in the register 303.
If the selector 317 has selected its input terminal connected to the selector 318 outputting data D322, on the other hand, the adder 302 adds the data D322 supplied by the selector 318 to the adder 302 by way of the selector 317 to the message D306 output by the selector 301 in order to produce a sum. By the way, the data D322 output by the selector 318 is data D202 (or u0i) received by the input port P301 as data D300. Thus, the adder 302 adds the received data D202 (or u0i) to the message D306 output by the selector 301 in order to produce a sum which is stored in the register 303.
As the operations described above are repeated for one column, data D307 having an amount equal to Σuj+u0i with the summation Σuj covering a range of j=1 to dv is accumulated in the register 303. The data D307 having an amount equal to Σuj+u0i is then transferred to a register 305 by way of a selector 304.
In the mean time, a delay FIFO 310 is used for delaying the message D306 output by the selector 301 as a message originated from a check node by keeping the message D306 in the delay FIFO 310 till new data D308 having an amount equal to Σuj+u0i with the summation Σuj covering a range of j=1 to dv is output by the register 305. The delay FIFO 310 then outputs the delayed message D306 to a subtractor 312 as a delayed input message D315.
The subtractor 312 subtracts the delayed input message D315 output by the delay FIFO 310 from the new data D308 output by the register 305 in order to produce a difference D316 having a magnitude equal to Σuj+u0i with the summation Σuj covering a range of j=1 to (dv−1). The subtractor 312 outputs the difference D316 to a selector 316. Then, the selector 316 outputs the difference D316 to the output port P303 as a message D321. Finally, the output port P303 passes on the message D321 as an output message D203 to the shift section 203 employed in the typical decoding apparatus shown in the block diagram of FIG. 10.
In other words, when carrying out the process of a variable node in accordance with Eq. (1), the node processor 210 serving as the variable node computes a message to be output to a specific check node through an edge by subtracting a message supplied by the specific check node from a sum of messages received from all check nodes connected to the node processor 210 serving as the variable node and the received data.
Next, the check-node process carried out by the node processor 210 serving as a check node is explained.
The node processor 210 receives one-row messages D205 originated by variable nodes from the message storage memory 204 of the typical decoding apparatus shown in the block diagram of FIG. 10 through the input port P302. The messages D205 are sequentially passed on by the input port P302 one message after another as messages D301 (or messages vi) and supplied to an LUT 300 as absolute values D303 (or |vi|).
The LUT 300 is an LUT for storing values of a non-linear function φ(x) used in Eq. (7) expressing the check-node process as values each associated with an argument x which is the absolute value D303 (or |vi|). That is to say, the LUT 300 is used for storing values D305 (or φ(|vi|). When an absolute value D303 (or |vi|) is supplied to the LUT 300, the LUT 300 outputs a value D305 (or φ(|vi|).
The value D305 (or φ(|vi|) read out from the LUT 300 is supplied to the adder 302 by way of the selector 301 as a message D306. The adder 302 adds the message D306 output by the selector 301 to data D323 output by the selector 317 in order to produce a sum which is then stored in the register 303. In this case, the selector 317 has selected its input terminal connected to the register 303 outputting data D307. Thus, the adder 302 adds the data D307 supplied by the register 303 to the adder 302 by way of the selector 317 to the message D306 output by the selector 301 in order to produce a sum which is then again stored in the register 303. Thus, the data D307 is a cumulative sum of the values D305 (or φ(|vi|).
As values D305 (or φ(|vi|) read out from the LUT 300 for messages D301 (or messages vi) for one row are cumulatively summed up to produce a one-line cumulative sum D307, the sum D307 having a magnitude equal to Σφ(|vi|) computed over a range of i=1 to dc is supplied to the register 305 by way of the selector 304.
In the mean time, the delay FIFO 310 is used for delaying the message D306 output by the selector 301 by keeping the message D306 in the delay FIFO 310 till new data D308 having an amount equal to Σφ(|vi|) computed over a range of i=1 to dc is output by the register 305. That is to say, the delay FIFO 310 is used for delaying the value D305 (or φ(|vi|) read out from the LUT 300. The delay FIFO 310 then outputs the delayed value D305 to the subtractor 312 as a delayed input message D315.
The subtractor 312 subtracts the delayed input message D315 from the new data D308 output by the register 305 in order to produce a difference D316 having a magnitude equal to Σφ(|vi|) computed over a range of i=1 to (dc−1). The subtractor 312 then outputs the difference D316 to an LUT 314.
The LUT314 is an LUT which works as follows. In the LUT 314, the difference D316 is treated as an argument x. For the argument x, the value of the inverse function φ−1(x) used in the check-node process according to Eq. (7) as the inverse function φ−1(x) of the nonlinear function φ(x) is read out from the LUT 314. To put in detail, when the subtractor 312 provides the LUT 314 with the difference D316 having a magnitude equal to Σφ(|vi|) computed over a range of i=1 to (dc−1), the LUT 314 outputs a value D318 (=φ−1(Σφ(|vi|))) which is the value of the inverse function φ−1(Σφ(|vi|)).
Concurrently with the operations described above, an EXOR circuit 306 carries out an exclusive logical sum process on the sign bit D304 (or a sign(vi)) of each message D301 (or each message vi) and a value D310 stored in a register 307 in order to produce a logical sum D309 and again stores the sum D309 in the register 307. The sign bit D304 of a message D301 is a bit indicating whether the message D301 is a positive or negative message.
As the sign bits of messages D301 (or messages vi) for one row are cumulatively summed up by the EXOR circuit 306 and stored in the register 307, the register 307 supplies a cumulative value D310 represented by πsign(vi) computed over a range of i=1 to dc to a register 309 by way of a selector 308.
In the mean time, the delay FIFO 310 is used for delaying the sign bit D304 (or the sign(vi)) used in the multiplication by keeping the sign bit D304 (or the sign(vi)) in the delay FIFO 310 till new data D311 represented by πsign(vi) computed over a range of i=1 to dc is output by the register 309. The delay FIFO 310 then outputs the delayed sign bit D304 to an EXOR circuit 315 as a delayed sign bit D313.
The EXOR circuit 315 carries out an exclusive logical sum process on the delayed sign bit D313 received from the delay FIFO 310 and a cumulative value D311 stored in the register 309 in order to produce a sign bit D319 and supplies the sign bit D319 represented by πsign(vi) computed over a range of i=1 to (dc−1) to the selector 316.
Finally, the selector 316 appends the sign bit D319 received from the EXOR circuit 315 to the value D318 (=φ−1(Σφ(|vi|))) output by the LUT 314 in order to produce a message D321 and outputs the message D321 to the output port P303 which then passes on the message D321 to the shift section 203 of the typical decoding apparatus shown in the block diagram of FIG. 10.
In other words, when carrying out the process of a check node in accordance with Eq. (7), the node processor 210 computes a message to be output to a specific variable node through an edge by subtracting a message supplied by the specific variable node from a sum of messages received from all check nodes connected to the node processor 210 serving the check node.
At the final stage of decoding, the node processor 210 carries out a process according to Eq. (5) in place of the variable-node process according to Eq. (1) and outputs data D308 resulting from the process as a decoding result D206 to the decoding-result storage memory 205 of the typical decoding apparatus shown in the block diagram of FIG. 10 by way of the output port P304. The final stage of decoding is typically the last variable-node process carried out after repeating the variable-node and check-node processes N times where N is an integer determined in advance.
It is to be noted that, even though the typical decoding apparatus shown in the block diagram of FIG. 10 is a decoding apparatus for decoding codes of P=6, a decoding apparatus for decoding P codes with P other than 6 can be basically designed to have a configuration identical with that of the typical decoding apparatus shown in the block diagram of FIG. 10.